package com.wwz.leetcode;

public class LeetCode31 {

    public static void main(String[] args) {
        int[] nums = {1,4,2,5,3};
        nextPermutation(nums);
        System.out.println(nums);
    }

    public static void nextPermutation(int[] nums) {
        int len = nums.length;
        // 从右往左找到第一个减小的数字
        int swapIndex = len - 1;
        for (int i = len - 2; i >= 0; i--) {
            if (nums[i] < nums[i + 1]) {
                swapIndex = i;
                break;
            }
        }
        // 没找到说明本身就是最大的，直接反转
        if (swapIndex == len - 1) {
            reverse(nums, 0, len - 1);
        } else {  // 找到了就与它左边更大的数交换，然后反转右边（升序变降序）
            for (int i = len - 1; i > swapIndex; i--) {
                if (nums[i] > nums[swapIndex]) {
                    swap(nums, swapIndex, i);
                    break;
                }
            }
            reverse(nums, swapIndex + 1, len - 1);
        }
    }

    public static void reverse(int[] nums, int start, int end) {
        while (start < end) {
            swap(nums, start++, end--);
        }
    }

    public static void swap(int[] nums, int m, int n) {
        int tmp = nums[m];
        nums[m] = nums[n];
        nums[n] = tmp;
    }

}
